package com.mgq.algorithm.dp;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给一-个包含n个整数元素的集合a，一个包含m个整数元素的集合b。
 * 定义magic操作为，从一个集合中取出一个元素，放到另一个集合里，且操作过
 * 后每个集合的平均值都大大于于操作前。
 * 注意以下两点:
 * 1)不可以把一个集合的元素取空，这样就没有平均值了
 * 2)值为x的元素从集合b取出放入集合a，但集合a中已经有值为x的元素，则a的
 * 平均值不变(因为集合元素不会重复)，b的平均值可能会改变(因为x被取出
 * 了)
 * 问最多可以进行多少次magic操作?
 */
public class MagicOperator {
    /**
     * magic操作
     * 这个题需要分析,是一道和业务相关的题
     * 首先 情况一:a的平均数=b的平均数.假设平均值100 把a的值拿出来给b
     *             a          b   平均值 100
     * 拿出<100     +          -         X
     * =100       不变                   X
     * >100       -变小
     *
     * 情况二: a的平均值<b的平均数.假设a平均值50,b平均值是100 把a的值拿出来给b
     *             a          b   a平均值50, b的平均值100
     * 拿出<50      +          -        X
     * >100        +          -        X
     * 50<c<100    -变小                X
     *
     * 情况三: a的平均值>b的平均数.假设a平均值100,b平均值是50 把a的值拿出来给b
     *              a         b   a平均值100, b的平均值50
     * 拿出<50      -          +         X
     * >100       +           -        X
     * 50<c<100   +           +      符合条件
     * 也就是说 a的平均值>b的平均值, 只能从a拿 50<c<100 放入b中.要实现最多可以进行多少次magic操作?
     * 应该每次从a中尽可能取出大于50最小的值,这样可以多取几次.
     * 例如: a中 有 60,70,80,90 这些数对a来说都是拖后腿的数.如果直接拿90过去,再拿80,b的平均值就可能变小了
     * 注意:这个题还有个技巧,应该转为double,否则精度丢失后,不准确
     * @param a
     * @param b
     * @return
     */
    public static int magic(int[] a, int[] b) {
        if (avg(a) == avg(b)) {
            return 0;
        }
        //不能这样写,题目要求能自行判断,因此我们应该自己找出大集合
       /* if (avg(a) < avg(b)) {
            return 0;
        }*/
        int[] arrMore = null;
        int[] arrLess = null;
        //需要找出2个集合那个大,从大的平均值集合取小与的平均值 给小集合
        if (avg(a) < avg(b)) {
            arrMore = b;
            arrLess = a;
        } else {
            arrMore = a;
            arrLess = b;
        }

        //排序,遍历的时候只要找到大于b的平均值的第一个数就是最小值
        Arrays.sort(arrMore);

        //把平均值较小的放入set中,保证搬的时候这个数不存在平均值较小的集合中
        Set<Integer> setLess = new HashSet<>();
        for (int i = 0; i < arrLess.length; i++) {
            setLess.add(arrLess[i]);
        }
        int answer = 0;
        int lengthMore = arrMore.length;
        int lengthLess = arrLess.length;
        double sumMore= Arrays.stream(arrMore).sum();
        double sumLess= Arrays.stream(arrLess).sum();
        double avgMore=avg(arrMore);
        double avgLess=avg(arrLess);

        double avgOldLess=0;

        for (int i = 0; i < lengthMore; i++) {
            if (avgLess>avgOldLess && arrMore[i] > avgLess && arrMore[i] < avgMore  && !setLess.contains(arrMore[i])) {
                //重新计算平均值
                lengthMore--;
                lengthLess++;
                setLess.add(arrMore[i]);
                System.out.println("大集合未拿:"+arrMore[i]+"之前的平均值是"+avgMore);
                System.out.println("小集合未加入:"+arrMore[i]+"之前的平均值是"+avgLess);

                avgOldLess=avgLess;
                avgMore=(sumMore-arrMore[i])/lengthMore;
                avgLess=(sumLess+arrMore[i])/lengthLess;
                if (avgLess > avgOldLess) {
                    System.out.println("拿走: "+arrMore[i]);
                    answer++;
                }
                System.out.println("大集合拿走:"+arrMore[i]+"之后的平均值是"+avgMore);
                System.out.println("小集合加入:"+arrMore[i]+"之后的平均值是"+avgLess);
            }
        }
        return answer;
    }

    public static double avg(int[] a) {
        return Arrays.stream(a).average().orElse(Double.NaN);
    }


    public static int magic2(int[] a, int[] b) {
        if (avg(a) == avg(b)) {
            return 0;
        }
        int[] arrMore = null;
        int[] arrLess = null;
        double sumMore=0;
        double sumLess=0;
        double sumA= Arrays.stream(a).sum();
        double sumB= Arrays.stream(b).sum();
        //需要找出2个集合那个大,从大的平均值集合取小与的平均值 给小集合
        if (avg(a) < avg(b)) {
            arrMore = b;
            arrLess = a;
            sumMore=sumB;
            sumLess=sumA;
        } else {
            arrMore = a;
            arrLess = b;
            sumMore=sumA;
            sumLess=sumB;
        }
        Set<Integer> setLess = new HashSet<>();
        for (int i = 0; i < arrLess.length; i++) {
            setLess.add(arrLess[i]);
        }
        int moreSize = arrMore.length;
        int lessSize = arrLess.length;
        int ops=0;
        for (int i = 0; i < arrMore.length; i++) {
            double cur = arrMore[i];
            if (cur < avg2(sumMore, moreSize) && cur > avg2(sumLess, lessSize) && !setLess.contains(cur)) {
                sumMore-=cur;
                moreSize--;
                sumLess += cur;
                lessSize++;
                setLess.add(arrMore[i]);
                ops++;
            }
        }
        return ops;
    }

    public static double avg2(double sum, int length) {
        return sum/length;
    }

    public static void main(String[] args) {
        int[] a = new int[]{50,60,70,80,200,400};
        int[] b = new int[]{30,40,50,90};
        int magic = magic(a, b);
        int magic2 = magic2(a, b);
        System.out.println(magic);
        System.out.println("----------------------");
        System.out.println(magic2);
    }
}
